# 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，
# 其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
# 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
#  返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替
# 代这个答案。
#  注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
#
#  示例 1：
# 输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0],
# queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
# 输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
# 解释：
# 条件：a / b = 2.0, b / c = 3.0
# 问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
# 结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
#
#  示例 2：
# 输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0],
# queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
# 输出：[3.75000,0.40000,5.00000,0.20000]
#
#  示例 3：
# 输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
# 输出：[0.50000,2.00000,-1.00000,-1.00000]
from typing import List


class Solution:
    def calcEquation2(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        """
        并查集
        将能彼此形成倍数关系元素合并成一组，并记录元素与代表元素直接的倍数关系
        :param equations:
        :param values:
        :param queries:
        :return:
        """
        class UnionFindSet:
            def __init__(self, n: int):
                self.parent = [_ for _ in range(n)]
                self.weight = [1.0] * n  # weight[i] = f 表示 i节点是其父节点(代表节点)的 f 倍

            def find(self, node: int) -> int:
                if self.parent[node] != node:
                    tmpOrigin = self.parent[node]
                    self.parent[node] = self.find(self.parent[node])
                    self.weight[node] *= self.weight[tmpOrigin]
                return self.parent[node]

            def union(self, node1: int, node2: int, value: float) -> None:
                p1, p2 = self.find(node1), self.find(node2)
                if p1 != p2:
                    self.parent[p1] = p2
                    self.weight[p1] = self.weight[node2] * value / self.weight[node1]

            def isConnected(self, node1: int, node2: int) -> float:
                p1, p2 = self.find(node1), self.find(node2)
                if p1 != p2:
                    return -1.0
                else:
                    return self.weight[node1] / self.weight[node2]

        dic, res, i = {}, [], 0
        for dividend, divisor in equations:  # 将条件涉及的所有被除数和除数都于一个索引进行映射，方便后续并查集进行聚合
            if dic.get(dividend) is None:
                dic[dividend] = i
                i += 1
            if dic.get(divisor) is None:
                dic[divisor] = i
                i += 1
        # print(dic)
        uf = UnionFindSet(len(dic))
        for index, (dividend, divisor) in enumerate(equations):
            uf.union(dic[dividend], dic[divisor], values[index])
        for dividend, divisor in queries:
            if dic.get(dividend) is not None and dic.get(divisor) is not None:
                res.append(uf.isConnected(dic[dividend], dic[divisor]))
            else:
                res.append(-1.0)
        return res

    def calcEquation1(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        """
        解法一：dfs遍历
        先根据equations和values进行建图（a / b = 2.0 表示 a->b 有向边为2.0; b->a 有向边为0.5）
        然后DFS遍历 queries 中提供的每个query，查看是否连通，并返回之间的倍数关系
        :param equations:
        :param values:
        :param queries:
        :return:
        """
        pass

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        return self.calcEquation1(equations, values, queries)


if __name__ == "__main__":
    equations = [["a", "b"], ["b", "c"]]
    values = [2.0, 3.0]
    queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

    equations = [["x1", "x2"], ["x2", "x3"], ["x1", "x4"], ["x2", "x5"]]
    values = [3.0, 0.5, 3.4, 5.6]
    queries = [["x2", "x4"], ["x1", "x5"], ["x1", "x3"], ["x5", "x5"], ["x5", "x1"],
               ["x3", "x4"], ["x4", "x3"], ["x6", "x6"], ["x0", "x0"]]
    print(Solution().calcEquation(equations, values, queries))
